package com.dy.分类.链表.回文链表;

import com.dy.分类.链表.ListNode;

/*
回文链表
请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false
示例 2:

输入: 1->2->2->1
输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
 */
public class Solution {
    public static boolean isPalindrome(ListNode head) {
        if(head==null){
            return true;
        }
        int count=0;
        ListNode p =head;
        while(p!=null){
            count++;
            p=p.next;
        }
        ListNode last=null;
        ListNode next;
        //逆序前半段
        for(int i =0;i<count/2;i++){
            next = head.next;
            head.next=last;
            last = head;
            head=next;
        }
        if(count%2!=0){
            head= head.next;
        }
        while(head!=null &&last!=null){
            if(head.val == last.val){
                head = head.next;
                last = last.next;
            }
            else{
                return false;
            }
        }
        return true;


    }
    //逆序后半段
    public static boolean isPalindrome2(ListNode head) {//O(n)、O(1)
        if (head == null || head.next == null)
            return true;
        ListNode slow = head, fast = head;
        while (fast.next!=null&&fast.next.next!=null ){//find mid node
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode last=null;
        ListNode next;
        while (slow!=null){//reverse
            next = slow.next;
            slow.next = last;
            last = slow;
            slow = next;
        }
        while (head!=null && last!=null){//check
            if (head.val != last.val){
                return false;
            }
            head = head.next;
            last = last.next;
        }
        return true;
    }
}
